package sliding_window

/*
1358.给你一个字符串 s，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都【至少】出现过一次的子字符串数目。

示例 1：
输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：
输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：
输入：s = "abc"
输出：1
*/

/*

 Time O(N)
 Space O(1)
*/
func numberOfSubstrings(s string) (ans int) {
	cnt, right, n := 0, 0, len(s)
	cht := [3]int{} //只包含三种字符

	for right < n {
		cht[s[right]-'a']++
		//a，b 和 c 都至少出现过一次
		for cht[0] > 0 && cht[1] > 0 && cht[2] > 0 {
			cht[s[cnt]-'a']-- //出现过一次了，-1
			cnt++             //都出现过一次，累加
		}
		right++
		ans += cnt
	}

	return
}

/*
Time O(N)
Space O(1)
*/
func numberOfSubstringsLastPos(s string) (ans int) {
	n := len(s)
	last := []int{-1, -1, -1} //记录最后出现的位置
	for i := 0; i < n; i++ {
		last[s[i]-'a'] = i //记录出现的位置
		//如果子串的结束索引为i,那么起始位置应该在min(last)的左边，这样才能有三个不同的字符
		//在这种情况下，起始索引的范围是[0, min(last)],
		ans += 1 + min(last[0], min(last[1], last[2])) //不同的起始索引代表不同的子串，区间范围都是结果
	}
	return
}
